<?php
// Author : evilair
// Time   : 2017/07/27

/*****************************************
*
* 在给定的字符串S中寻找最长的回文子串
* 可以假设S的最大长度是1000
* 存在唯一的最长回文子串
*****************************************/

function find_palindrome($str, $low, $high) {
  $maxLen = strlen($str);
  while($low >= 0 && $high < $maxLen && $str[$low] == $str[$high]) {
    $low--;
    $high++;
  }
  $substr = substr($str, $low + 1, $high - $low -1);
  return $substr;
}

function find_long_palndrome($str) {
  $maxLen = strlen($str);
  if ($maxLen <= 1) {
    return $str;
  }
  $maxsubstring = '';
  $substring = '';
  for ($i = 0; $i < $maxLen; $i++) {
    $substring = find_palindrome($str, $i, $i);
    if (strlen($maxsubstring) < strlen($substring)) {
      $maxsubstring = $substring;
    }
  }
  for ($i = 0; $i < $maxLen; $i++) {
    $substring = find_palindrome($str, $i, $i+1);
    if (strlen($maxsubstring) < strlen($substring)) {
      $maxsubstring = $substring;
    }
  }
  return $maxsubstring;
}
$teststr = 'abccbbccaa';
$res = find_palindrome($teststr, 4, 5);
echo $res;
echo "\n";
$res = find_long_palndrome($teststr);
echo $res;
?>